package com.julius.design.suanfa;

import java.time.LocalTime;
import java.util.*;

public class Solution {


    public static int majorityElement(int[] nums) {
        //排序
        Arrays.sort(nums);
        int length = nums.length;
        if(length == 1){
            return nums[0];
        }
        //遍历
        int temp = 0;
        int result = 1;
        for(int i = 0;i<length;i++){
            int current = nums[i];
            if(i == 0){
                temp = current;
                continue;
            }
            if(current == temp){
                result++;
            }else{
                result = 1;
            }
            temp = current;
            if(result > length/2){
                return current;
            }
        }
        return 0 ;
    }

    public int majorityElement2(int[] nums) {
        //定义一个map,key为数值，value指该值存在的格式
        Map<Integer,Integer> map = new HashMap<>(1<<4);
        //遍历
        int length = nums.length;
        for(int i = 0;i<length;i++){
            int key = nums[i];
            if(map.containsKey(key)){
                int value = map.get(key);
                value++;
                //存在将数量累加
                map.put(key, value);
            }else{
                //不存在则新增
                map.put(key, 1);
            }
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > length/2){
                return entry.getKey();
            }
        }
        return 0 ;
    }

    /**
     * 两数相加
     * @param num
     * @return
     */
    public static int addDigits(int num){
        //基础条件
        if(num < 10){
            return num;
        }
        int tempNum = 0;
        //数学方式求出每个位置的值
        String string = ""+num;
        char[] chars = string.toCharArray();
        for(char c : chars){
            int temp = c - '0';
            tempNum+=temp;
        }
        return addDigits(tempNum);
    }

    /**
     * 使用循环处理
     * @param num
     * @return
     */
    public static int addDigits2(int num){
        //固定循环条件
        while(num >= 10){
            int tempNum = 0;
            //使用数学方式找出各位的值并相加,从后往前查找
            while(num > 0){
                //对10取余找出个位数字
                tempNum+=num%10;
                //将数字进行降幂
                num = num/10;
            }
            num = tempNum;
        }
        return num;
    }


    /**
     * 整数翻转
     * @param x
     * @return
     */
    public static int reverse(int x) {
        int rev = 0;
        //取出各个位上的数字
        while(x != 0){
            //需要判断是否超过范围
            if(rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10){
                return 0;
            }
            //数学方式弹出
            int digit = x % 10;
            x = x / 10;
            //数学方式压入
            rev = rev * 10 + digit;
        }
        return rev;
    }

    /**
     * 回文数
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        //首先负数肯定不是回文数
        if(x < 0 || (x % 10 == 0 && x != 0)){
            return false;
        }
        int pre = x;
        //整数翻转
        int rev = 0;
        while(x != 0){
            //防止越界
            if(rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10){
                return false;
            }
            //数学出栈
            int digit = x % 10;
            x = x / 10;
            //数学压栈
            rev = rev * 10 +digit;
        }
        return rev == pre;
    }

    /**
     * 罗马数字转为整数
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        //遍历字符串  罗马数字中小的数字在大的数字的右边
        Character pre = null;
        int preIndex = 0;
        int result = 0;
        for(int i = 0;i<s.length();i++){
            if(i == 0 || pre == null){
                pre =s.charAt(i);
                preIndex = getValue(pre);
                continue;
            }
            Character cur = s.charAt(i);
            int curIndex = getValue(cur);
            //如果前面的比后面的小，则要组合起来计算，否则先加上前置结果
            if(curIndex > preIndex){
                result += (curIndex-preIndex);
                pre = null;
            }else{
                result += preIndex;
                pre = cur;
                preIndex = curIndex;
            }
        }
        //防止最后一个无法加上
        if(pre != null){
            result += preIndex;
        }
        return result;
    }

    /**
     * 性能高于HashMap
     * @param c
     * @return
     */
    public static int getValue(char c){
        switch(c){
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default :
                return 0;
        }
    }


    /**
     * [14] 最长公共前缀
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        /**
         * 思路：
         *      穷举依次比较前缀，拆分两两比较
         */

        if(strs.length == 0){
            return "";
        }
        //前缀缓存
        String prefix = strs[0];

        //穷举
        for(int i = 1;i<strs.length;i++){
            //如何比较两个字符串的最长公共前缀
            prefix = getPrefix(prefix, strs[i]);
            if(prefix.length() == 0){
                return prefix;
            }
        }
        return prefix;
    }

    /**
     * 获取两个字符串的最长公共前缀
     * @return
     */
    public static String getPrefix(String str1,String str2){
        int length1 = str1.length();
        int length2 = str2.length();
        if(length1 == 0 || length2 == 0){
            return "";
        }
        int i = 0 ;
        StringBuilder prefix = new StringBuilder();
        while(i < length1 && i < length2){
            char a = str1.charAt(i);
            if(a == str2.charAt(i)){
                prefix.append(a);
            }else{
                break;
            }
            i++;
        }
        if(prefix.length() == 0){
            return "";
        }
        return prefix.toString();

    }

    /**
     * [20] 有效的括号
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        /**
         * 如果一个括号的打开的右边是关闭，则必须是相同类型
         * 最后比较每种类型的开和关的个数是否相同
         * '('，')'，'{'，'}'，'['，']'
         */
        if(s.length() <= 1 || s.length() %2 != 0){
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if(isOpen(c)){
                //入栈
                stack.push(c);
            }else{
                //出栈
                //右括号时，如果栈为空或者右括号不匹配，直接返回false
                if(stack.isEmpty() ||  c != isMatch(stack.peek())){
                    return false;
                }
                //弹出
                stack.pop();
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }

    /**
     * 判断是否为开字符
     * @param character
     * @return true 开，false 关
     */
    public static boolean isOpen(Character character){
        switch(character){
            case '(':
                return true;
            case '{':
                return true;
            case '[':
                return true;
            case ')':
                return false;
            case '}':
                return false;
            case ']':
                return false;
            default: return false;
        }
    }

    /**
     * 判断是否匹配
     * @param character
     * @return
     */
    public static Character isMatch(Character character){
        switch(character){
            case '(':
                return ')';
            case '{':
                return '}';
            case '[':
                return ']';
            default: return '1';
        }
    }


    /**
     * [21] 合并两个有序链表
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //临界判断
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        //穷举链表 双指针法
        ListNode newHead = new ListNode(-1);
        ListNode newCur = newHead;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                newCur.next = cur1;
                cur1 = cur1.next;
            }else{
                newCur.next = cur2;
                cur2 = cur2.next;
            }
            //断掉之前的链
            newCur = newCur.next;
        }
        if(cur1 == null){
            newCur.next = cur2;
        }
        if(cur2 == null){
            newCur.next = cur1;
        }
        return newHead.next;
    }


    public static int strStr(String haystack, String needle) {
        int haystackLength = haystack.length();
        int needleLength = needle.length();
        //临界条件
        if(needleLength == 0){
            return 0;
        }
        if(haystackLength < needleLength){
            return -1;
        }

        //遍历
        int j = 0;
        char temp = needle.charAt(j);
        int index = 0;
        for (int i = 0; i < haystackLength; i++) {
            if(haystack.charAt(i) == temp){
                if(j == 0){
                    index = i;
                }
            }else{
                j = 0;
                index = 0;
                temp = needle.charAt(j);

                continue;
            }
            if(j == needleLength-1){
                return index;
            }
            j++;
            temp = needle.charAt(j);
            //剩余字符串已经不能匹配全字符串
            // if(haystackLength-needleLength > i+1){
            //     return -1;
            // }
        }
        return -1;
    }


    public static void main(String[] args) {
        int all = 500000;
//        System.out.println(money(all));



        int result = LocalTime.parse("20:41:00").toSecondOfDay()-LocalTime.parse("09:30:00").toSecondOfDay()+
                LocalTime.parse("20:21:00").toSecondOfDay()-LocalTime.parse("09:39:00").toSecondOfDay()+
                LocalTime.parse("20:42:00").toSecondOfDay()-LocalTime.parse("09:23:00").toSecondOfDay()+
                LocalTime.parse("20:09:00").toSecondOfDay()-LocalTime.parse("09:17:00").toSecondOfDay()+
                LocalTime.parse("20:05:00").toSecondOfDay()-LocalTime.parse("09:19:00").toSecondOfDay()+

                LocalTime.parse("20:51:00").toSecondOfDay()-LocalTime.parse("09:21:00").toSecondOfDay()+
                LocalTime.parse("21:07:00").toSecondOfDay()-LocalTime.parse("09:29:00").toSecondOfDay()+
                LocalTime.parse("18:54:00").toSecondOfDay()-LocalTime.parse("10:13:00").toSecondOfDay()+
                LocalTime.parse("20:12:00").toSecondOfDay()-LocalTime.parse("09:24:00").toSecondOfDay()+
                LocalTime.parse("20:11:00").toSecondOfDay()-LocalTime.parse("09:53:00").toSecondOfDay()+

                LocalTime.parse("21:02:00").toSecondOfDay()-LocalTime.parse("09:41:00").toSecondOfDay()+
                LocalTime.parse("20:18:00").toSecondOfDay()-LocalTime.parse("09:32:00").toSecondOfDay()+
                LocalTime.parse("18:26:00").toSecondOfDay()-LocalTime.parse("09:30:00").toSecondOfDay()+
                LocalTime.parse("20:33:00").toSecondOfDay()-LocalTime.parse("09:54:00").toSecondOfDay()+
                LocalTime.parse("20:24:00").toSecondOfDay()-LocalTime.parse("09:31:00").toSecondOfDay()+

                LocalTime.parse("19:29:00").toSecondOfDay()-LocalTime.parse("10:21:00").toSecondOfDay()+
                LocalTime.parse("23:59:59").toSecondOfDay()-LocalTime.parse("09:55:00").toSecondOfDay()+
                LocalTime.parse("17:01:00").toSecondOfDay()-LocalTime.parse("09:32:00").toSecondOfDay()+
                LocalTime.parse("19:00:00").toSecondOfDay()-LocalTime.parse("09:25:00").toSecondOfDay()+
                LocalTime.parse("19:48:00").toSecondOfDay()-LocalTime.parse("09:34:00").toSecondOfDay()+
                LocalTime.parse("21:17:00").toSecondOfDay()-LocalTime.parse("09:20:00").toSecondOfDay()+
                LocalTime.parse("19:54:00").toSecondOfDay()-LocalTime.parse("09:20:00").toSecondOfDay();
        System.out.println(result/(60*60*22.00));

    }


    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


    /**
     * 奖金计算
     * @param all
     * @return
     */
  public static double money(int all){
      //0.2
      int base1 = 131040;
      //0.25
      int base2 = 209664;
      //0.3
      int base3 = 299520;
      //0.35
      int base4 = 449280;
      //0.4 溢出
      int base5 = 599040;
      double result;
      if(all > base5){
          result = 0.4*(all-base5)+0.35*(base5-base4)+0.3*(base4-base3)+0.25*(base3-base2)+0.2*(base2-base1);
      }else if(all >= base4 && all < base5){
          result = 0.35*(all-base4)+0.3*(base4-base3)+0.25*(base3-base2)+0.2*(base2-base1);
      }else if (all >= base3 && all < base4){
          result = 0.3*(all-base3)+0.25*(base3-base2)+0.2*(base2-base1);
      }else if (all >= base2 && all < base3){
          result = 0.25*(all-base2)+0.2*(base2-base1);
      }else if (all >= base1 && all < base2){
          result = 0.2*(all-base1);
      }else {
          return 0;
      }
      return result;
  }




}
